#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
        if (n1 + n2 != n3) return false;

        vector<vector<bool>> dp(n1 + 1, vector<bool>(n2 + 1));

        s1 = ' ' + s1;
        s2 = ' ' + s2;
        s3 = ' ' + s3;

        dp[0][0] = true;
        for (int i = 1; i <= n2; i++)
            if (s2[i] == s3[i]) dp[0][i] = true;
            else break;
        for (int i = 1; i <= n1; i++)
            if (s1[i] == s3[i]) dp[i][0] = true;
            else break;

        for (int i = 1; i <= n1; i++)
            for (int j = 1; j <= n2; j++)
                dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j])
                || (s2[j] == s3[i + j] && dp[i][j - 1]);

        // for(auto e : dp)
        // {
        //     for(auto c : e){
        //         cout << c << ' ';
        //     }
        //     cout << endl;
        // }

        return dp[n1][n2];
    }
};

// 1 - - - - i
// 1 - - - - j
// 1 - - - - - - - - - (i+j)